游戏寻路算法

Graph

Graph是一种可以表示AI可通过的世界的各个部分的数据结构。每个Graph包含一组Node，这些Node通过“边”相互连接，这些便可以是无向的也可以是有向的。

CRE：游戏开发中使用的Waypoints就是一种GraphNode。

广度优先搜索

广度优先搜索(BFS)算法只有在较近的节点都检查完毕时，才会考虑更远的节点。

广度优先搜索算法可以保证：无论各边是否加权，还是各边是否具有相同的正权，总能找到最短路径。

广度优先搜索算法，通常使用队列(Queue)来实现。

贪婪最佳优先搜索（Greedy Best-First Search）

贪婪最佳优先搜索(Greedy Best-First Search,GBFS)是一种启发式搜索算法。

这种算法不保证找到最短路径。

cRE：算是深度优先搜索的一种变体。

• 启发函数(Heuristic Funcition)

这个评估函数用于估计从当前节点到目标节点的距离或成本。通常情况下，启发函数是基于节点的某种特征或属性，比如节点到目标的直线距离（在A*搜索中常用的一种启发函数）。

• 搜索过程

• 开始时，将起始节点放入优先级队列中（根据启发函数值的大小排序，最小的优先）。
• 重复执行以下步骤：
  • 从优先级队列中取出启发函数值最小的节点。
  • 如果该节点是目标节点，搜索结束。
  • 否则，扩展该节点，将其所有未访问的相邻节点加入优先级队列中。
• 如果队列为空而未找到目标节点，则任务失败。

A*搜索

对贪婪最佳优先搜索做一些修改，可以将其转换为A*搜索。

A*搜索同时考虑了从起始节点到当前节点的实际成本（通常表示为 g 值），而贪婪最佳优先搜索只关注启发函数的值，不考虑实际成本。

A*搜索算法能找到最短路径。A*算法通过维护每个节点到起始节点的实际路径成本，确保每个节点的路径成本是已知的最小值。

公式表示：$f(x) = g(x) + h(x)$。当选择一个新的current节点时，A/*会选择具有最低$f(x)$值的节点。也就是$g(x)$节点x的路径成本和$h(x)$启发函数之和。

迪杰斯特拉算法(Dijkstra)

迪杰斯特拉算法（Dijkstra’s algorithm）是一种用于计算图中单源最短路径的经典算法。它被命名为荷兰计算机科学家艾兹赫尔·迪杰斯特拉（Edsger W. Dijkstra）。

如果问题中图的边权重非负且要求找到起始节点到所有其他节点的最短路径，且没有额外的启发信息，Dijkstra算法是更合适的选择。
如果问题中有明确的目标节点，并且能够设计良好的启发函数来指导搜索方向，A*搜索算法则可能更为合适，特别是在需要快速找到一条路径的实时应用中。

Dijkstra算法能够确保找到起始节点到所有其他节点的最短路径，适用于没有启发信息的一般图。

其他图形表示法

Waypoints表示法是随着FPS的出现而流行的。使用Waypoints的主要缺点是AI只能移动到节点的附近或者边上。即使路径形成了三角形，也不能保证三角形内部都是有效位置。

导航网格(Nav Mesh)是另一种表示形式。这种方法中，Graph中的每个节点都对应一个凸多边形。相邻节点是任何相邻的凸多边形。使用导航网格，AI可以安全地前往多边形内部任何位置。具有很高的可操作性。

（END）